package com.leetcode.根据算法进行分类.数学定理相关;

import java.util.Arrays;

/**
 * @author: ZhouBert
 * @date: 2021/1/20
 * @description: 628. 三个数的最大乘积
 * https://leetcode-cn.com/problems/maximum-product-of-three-numbers/
 */
public class A_628_三个数的最大乘积 {

	public static void main(String[] args) {
		String dominoes = "RR.L";
		A_628_三个数的最大乘积 action = new A_628_三个数的最大乘积();
		String res = action.pushDominoes(dominoes);
		System.out.println("res = " + res);
	}

	/**
	 * 由于有负数的情况，进行讨论：
	 * 1.num(负数) == 0 -> 最大三个
	 * 2.num(负数) == 1 -> 最大三个
	 * 3.num(负数) == 2 -> 最小两个 + 最大的一个 || 最大三个
	 * 4.num(负数) > 2 -> 最小两个 + 最大的一个 || 最大三个
	 *
	 * @param nums
	 * @return
	 */
	public int maximumProduct(int[] nums) {
		Arrays.sort(nums);
		return Math.max(nums[nums.length - 1] * nums[nums.length - 2] * nums[nums.length - 2]
				, nums[nums.length - 1] * nums[0] * nums[1]);
	}


	/**
	 * 推多米诺牌
	 * https://leetcode-cn.com/problems/push-dominoes/
	 * ---
	 * 1.要么从 L/R 入手，要么从 . 入手。看起来从 . 入手比较方便
	 *
	 * @param dominoes
	 * @return
	 */
	public String pushDominoes(String dominoes) {
		char[] chars = dominoes.toCharArray();
		int len = chars.length;
		for (int i = 0; i < len; i++) {
			//1.寻找 . 段的第一个位置
			if (chars[i] == '.') {
				//2.判断是否有 left 的 push
				boolean leftPush = i > 0 && chars[i - 1] == 'R';
				//3.开始寻找 . 段的最后一个位置
				int j = i + 1;
				for (; j < len; j++) {
					if (chars[j] != '.') {
						break;
					}
				}
				//此时 j 就是 开区间
				boolean rightPush = j < len && chars[j] == 'L';
				if (leftPush && !rightPush) {
					//只有左边的 push
					for (; i < j; i++) {
						chars[i] = 'R';
					}
				} else if (!leftPush && rightPush) {
					//只有右边的 push
					for (; i < j; i++) {
						chars[i] = 'L';
					}
				} else if (leftPush && rightPush) {
					//如果 两边都有 push
					//使用两个指针
					int begin = i;
					int end = j - 1;
					while (begin < end) {
						chars[begin++] = 'R';
						chars[end--] = 'L';
					}
					i = j;
				}
			}
		}
		return new String(chars);
	}
}
